МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
МЕТОД НЬЮТОНА ДЛЯ РОЗВ’ЯЗУВАННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ
Інструкція
до лабораторної роботи № 5
з курсу
"Комп’ютерні методи дослідження інформаційних процесів та систем"
для студентів спеціальності 6.1601
"Інформаційна безпека"
Затверджено
на засіданні кафедри
«Захист інформації»
Протокол № ___ від __________.
Львів – 2007
Метод Ньютона для розв’язування систем нелінійних рівнянь: Інструкція до лабораторної роботи №5 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів спеціальності 6.1601 "Інформаційна безпека" / Укл.: Л.В.Мороз, З.М.Стрілецький, В.М.Іванюк - Львів: НУЛП, 2007.- 11 с.
Укладачі: Леонід Васильович Мороз, к.т.н., доц.
Зеновій Михайлович Стрілецький, к.т.н., доц.
Іванюк Віталій Миколайович, асистент.
Відповідальний за випуск: І.Я. Тишик, ст.в.
Рецензент: В.Б.Дудикевич, д.т.н., проф.,
В.В.Хома, д.т.н., проф.
Мета роботи - ознайомлення з найпоширенішим ітераційним методом розв’язування систем нелінійних рівнянь – методом Ньютона.
Вступ
Систему нелінійних рівнянь у загальному випадку можна зобразити у вигляді
EMBED Equation.3
Тобто як EMBED Equation.3 функцій EMBED Equation.3 від EMBED Equation.3 невідомих EMBED Equation.3 , причому функції EMBED Equation.3 не обов’язково лінійно залежить від змінних EMBED Equation.3 .
Позначимо вектор змінних через EMBED Equation.3 , а вектор функції через EMBED Equation.3 . Тоді систему (1) можна записати у формі.
EMBED Equation.3
Завдання полягає в тому, щоб знайти розв’язок цієї системи. Слід сказати, що на даний час не існує математичної теорії, яка дозволяла б у загальному вигляді розв’язати питання про існування та число розв’язків системи (2). Їх може не бути зовсім, може бути один, декілька або нескінчена множина [3]. Крім того, важливою особливістю системи нелінійних рівнянь є те, що для їх розв’язків не можна використати прямі методи, зокрема, метод послідовного виключення невідомих. Усі розробленні методи є ітераційними, а найефективнішим і широко вживаним є метод Ньютона.
1. Стандартний метод Ньютона
Метод Ньютона базується на лінеаризації задачі і заміні розв'язування нелінійної системи (2) на послідовність розв'язувань лінійних систем (найчастіше прямими методами).
Будемо вважати, що система рівнянь (2) має розв'язок; позначимо його через вектор EMBED Equation.3 і розкладемо кожну функцію в ряд Тейлора в околі розв'язку
EMBED Equation.3
де EMBED Equation.3 - члени другого і вищих порядків.
Вважаючи, що EMBED Equation.3 дуже близьке до EMBED Equation.3 , знехтуємо членами вищих порядків і запишемо систему рівнянь в лінеаризованій формі:
EMBED Equation.3 (3)
або в іншому вигляді
EMBED Equation.3 (4)
де
EMBED Equation.3 – матриця Якобі (якобіан) системи (1)
Враховуючи, що EMBED Equation.3 є розв'язком системи, згідно з (2) можемо записати:
EMBED Equation.3
Звідси випливає, що і праву частину (4) також можна прирівняти до нуля:
EMBED Equation.3 (5)
Розв'язком системи (5) є нове значення вектора X, яке не точно дорівнює значенню вектора EMBED Equation.3 (оскільки знехтували членами другого і вищих порядків). Використовуючи верхні індекси для позначення послідовності ітерацій, можна записати
EMBED Equation.3 (6)
Звідси
EMBED Equation.3 (7)
де EMBED Equation.3 - обернена матриця Якобі; EMBED Equation.3 .
У достатньо широкому околі розв'язку EMBED Equation.3 ітераційний процес (7) збігається, якщо EMBED Equation.3 .
Ітераційний процес закінчується при виконанні умови
EMBED Equation.3 (8)
де Σ - задана гранична похибка уточнень коренів системи (1).
Таким чином, алгоритм стандартного методу Ньютона можна розбити, на декілька кроків.
Крок 1. Вибір вектора початкових уточнень
EMB...